package com.cuz.daileetcode;

public class Day53 {

    /**
     * 调整数据使相邻数乘积为4的倍数
     */
    public static class AdjustAbledjacentNumbersIsAMultipleOf4 {

        public static boolean solution1(int[] arr) {
            if (arr == null || arr.length == 0) {
                return true;
            }
            if (arr.length == 1 && arr[0] == 2) {
                return false;
            }
            int multipleOf2 = 0;
            int oddNumber = 0;
            int multipleOf4 = 0;
            for (int temp : arr) {
                if (isMultipleOf2ButNo4(temp)) {
                    multipleOf2++;
                } else if (isMultipleOf4(temp)) {
                    multipleOf4++;
                } else {
                    oddNumber++;
                }
            }
            if (multipleOf2 != 0) {
                return multipleOf4 >= oddNumber;
            } else {
                return multipleOf4 >= oddNumber - 1;
            }
        }

        private static boolean isMultipleOf2(int num) {
            return (num & 1) == 0;
        }

        private static boolean isMultipleOf4(int num) {
            return (num & 3) == 0;
        }

        private static boolean isMultipleOf2ButNo4(int num) {
            return ((num & 1) == 0) && ((num & 3) != 0);
        }

        public static void main(String[] args) {
            System.out.println(isMultipleOf2ButNo4(4));
            System.out.println("yes");
        }
    }

    /***
     * 二维数组向右or向下沿途路径数字之和最小值
     */
    public static class MinimumPathSum {

        public static void main(String[] args) {
            //0  1   1   1
            //2  2   2   100
            //2  2   4    3
            int[][] arr = {
                    {0, 1, 1, 1},
                    {2, 6, 10, 100},
                    {2, 3, 4, 3},
            };
            System.out.println(solution1(arr));
            System.out.println(solution2(arr));
        }

        public static int solution2(int[][] arr) {
            if (arr == null || arr.length == 0 || arr[0].length == 0) {
                return 0;
            }
            int rowMax = arr.length;
            int colMax = arr[0].length;
            int[] dp = new int[colMax];
            //初始化dp 第一行
            dp[0] = arr[0][0];
            for (int index = 1; index < colMax; index++) {
                dp[index] = arr[0][index] + dp[index - 1];
            }
            int row = 1;
            while (row < rowMax) {
                for (int index = 0; index < colMax; index++) {
                    if (index == 0) {
                        //左侧的列只能从上走到下
                        dp[index] = dp[index] + arr[row][index];
                    } else {
                        //这个时候dp[index]还没更新 dp[index]表示上一行
                        //dp[index - 1]表示左边一行
                        dp[index] = Math.min(dp[index], dp[index - 1]) + arr[row][index];
                    }
                }
                row++;
            }
            return dp[colMax - 1];
        }

        public static int solution1(int[][] arr) {
            if (arr == null || arr.length == 0 || arr[0].length == 0) {
                return 0;
            }
            int rowMax = arr.length;
            int colMax = arr[0].length;
            int[][] dp = new int[rowMax][colMax];
            for (int row = 0; row < rowMax; row++) {
                for (int col = 0; col < colMax; col++) {
                    if (row == 0 && col == 0) {
                        dp[0][0] = arr[0][0];
                        continue;
                    }
                    if (row == 0) {
                        dp[0][col] = arr[0][col] + dp[0][col - 1];
                        continue;
                    }
                    if (col == 0) {
                        dp[row][0] = arr[row][0] + dp[row - 1][0];
                        continue;
                    }
                    dp[row][col] = Math.min(dp[row - 1][col], dp[row][col - 1]) + arr[row][col];
                }
            }
            return dp[rowMax - 1][colMax - 1];
        }
    }
}
